package com.LeeCode;

/**
 * 二叉搜索子树的最大键值和
 */

public class Code1373 {
    public static void main(String[] args) {
        Integer[] arr = {1, 4, 3, 2, 200, 2, 5, null, null, null, null, null, null, 4, 6};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1373().maxSumBST(root));
    }

    private int ans = Integer.MIN_VALUE;

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return Math.max(ans, 0);
    }

    private Result dfs(TreeNode root) {
        if (root == null)
            return new Result(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);

        Result left = dfs(root.left);
        Result right = dfs(root.right);
        if (left.isBST && right.isBST && left.maxVal < root.val && root.val < right.minVal) {
            int sum = root.val + left.sum + right.sum;
            int minVal = Math.min(root.val, left.minVal);
            int maxVal = Math.max(root.val, right.maxVal);
            ans = Math.max(ans, sum);
            return new Result(true, minVal, maxVal, sum);
        } else {
            return new Result(false, 0, 0, 0);
        }
    }

    class Result {
        boolean isBST;
        int minVal;
        int maxVal;
        int sum;

        Result(boolean isBST, int minVal, int maxVal, int sum) {
            this.isBST = isBST;
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.sum = sum;
        }
    }
}
